Programmable Logic Arrays (PLAs) have been used in the semiconductor industry for many years. They are essentially generic electronic circuits, able to be programmed to provide a variety of logic functions. PLAs are well understood in the art, but a brief explanation is provided below.
In PLAs, a logic function to be implemented is expressed in product terms (AND terms) and sum terms (OR terms). Each product term is generated by circuitry that can be programmed to form the AND of any subset of the inputs to the PLA and their complements. Product terms are then be summed, or OR'd, through additional programmable circuitry.
More specifically, PLAs are generally constructed in the form of regular arrays, with the input lines being orthogonal to the product lines, as shown in the generalized circuit diagram of FIG. 1. FIG. 1 shows one type of PLA known as a PAL. In FIG. 1, PAL 100 includes inputs 102, A–D, where each input and its complement is input into programmable AND array 104 on lines 106. AND lines 108 are formed orthogonal to lines 106. When a selected intersection between an input-term line 106 and an AND line 108 is programmed, then “AND terms” or “product terms” 110 are formed. The product terms 110 are then fed into OR gates 112, forming “sum terms” 114.
As is understood in the art, product-terms are often implemented with a wired-OR mechanism, where at each intersection of lines 106 and 108 programmable transistors 115 are used. A pull-up 116 is also used, as shown in the generalized circuit diagram of FIG. 2. Although the pull-up 116 is shown as a resistor in FIG. 2, frequently a passive pull-up is implemented with a biased P-channel transistor instead. It will be noted that when using the structure of FIG. 2, the AND gates 109 shown in FIG. 1 are not actually physically present, but instead in FIG. 1 AND gates 109 represent logically the function being performed.
A second type of PLA structure (sometimes referred to as a “Full PLA”) is shown in FIG. 3, having both a programmable AND array 104 and a programmable OR array 117. In other words, both product terms and sum terms can be programmed. Thus, the device of FIG. 3 can implement any set of combinational logic limited only by the number of inputs, outputs, and product terms.
Relative to the device of FIG. 1, the device of FIG. 3 sacrifices some speed, but has greater programming flexibility and is better for implementing state machines. As well, unlike the FIG. 1 device, in the FIG. 3 device, each product term can be used by, or shared among, all sum terms. Still, as shown in FIG. 4, some PLA devices create OR arrays where selected groups of the product terms are shared among selected groups of the sum terms.
Flexibility of PLA structures, including those of FIGS. 1 and 3, can be further enhanced by adding flip-flops 118 (shown in FIG. 3) to one or more of the outputs to create general-purpose sequential circuits. As shown in FIG. 5, inverted product terms such as !PT can also be fed back directly into the AND array. As used herein, complemented terms will be indicated with either a “!” or with an overbar, as is the practice in the art. As shown in FIG. 5a, when many product terms are inverted and fed back, it forms what is known as a NAND—NAND (or NOR—NOR) array.
Many PLA devices also include post-array logic structures as shown in FIG. 6. The most frequent need for such structures is to complement a logic function—otherwise, to complement the function, one would have to resort to DeMorgan's Law (!(AB)=(!A+!B)), typically resulting in a large number of product terms that would need to be programmed. XOR gates 120 are commonly used as such post-array structures. Inversion can be controlled by (1) a sum term representing a complex function (as for XOR gate 1201), (2) a single product term (as for XOR gate 1202), or (3) by a single logic value that can be programmed to a logical “1” (Vdd) or “0” (Vss) (as for XOR gate 1203).
Similarly, pre-array logic structures 122 are also often used as shown in FIG. 7. Such pre-array logic structures are often useful in performing arithmetic functions such as accumulators. Both post-array and pre-array logic structures are used to reduce the number of product terms that would otherwise be required, and hence allow the use of smaller and faster PLA devices.
Each of the conventional PLA structures described in FIGS. 1–7 is usually a discrete device and is programmable and reprogrammable by the user either using a specialized programming device or in-system as is understood in the art. As should be understood in the art from FIGS. 1–7, there are numerous types of PLAs available and those described are exemplary only.
As alluded to above with the discussion of pre- and post-array structures, it is generally desirable to use the smallest PLA device available, for real-estate reasons as well as speed. To that end, “PLA folding” has been studied and is described in Ferreira and Song, “Achieving Optimality for Gate Matrix Layout and PLA Folding: a Graph Theoretic Approach”, 1992. In general, PLA folding is a technique that, given a PLA, attempts to produce an equivalent PLA that occupies less space. For example, consider the following logic functions to be implemented by a PLA:f6={overscore (v)}1v5+{overscore (v)}2{overscore (v)}3+v1v3+{overscore (v)}5f7=v2v4+{overscore (v)}2{overscore (v)}4These functions are shown implemented in a traditional PLA in FIG. 8, where the “dots” represent a programmed connection. Through a series of matrix manipulation and rearranging of rows, the result of the folding is shown in FIG. 9. More details of this example can be found in Ferreira and Song (cited above). As shown in FIG. 9, the folded PLA is much more compact, retaining as much physical regularity as possible by causing the tiling of product term groupings.
Still, this PLA folding technique has gained little practical application. To effectively use folding, an engineer must know with relative certainty the functions to be programmed. And the freedom to make changes to the functionality is severely limited by the “folds.” Moreover, PLAs are typically only available as discrete devices (e.g., PLDs) in fixed sizes with fixed characteristics. So while folding techniques might be useful in theory, there are essentially no devices using them.